#include <bits/stdc++.h>
using namespace  std;

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
    BSTNode(const K& key = K(), const V& value = V())
    : _pLeft(nullptr) , _pRight(nullptr), _key(key), _value(value)
    {

    }
    BSTNode<K,V>* _pLeft;
    BSTNode<K,V>* _pRight;
    K _key;
    V _value;
};
template<class K, class V>
class BSTree
{
        typedef BSTNode<K, V> Node;
        typedef Node* PNode;
        PNode _pRoot;
    public:
        BSTree(): _pRoot(nullptr){}
        PNode Find(const K& key)
        {
            PNode pNode = _pRoot;
            while (pNode != nullptr )
            {
                if (pNode->_key < key)
                {
                    pNode = pNode->_pRight;
                }
                else if(pNode->_key > key)
                {
                    pNode = pNode->_pLeft;
                }
                else
                {
                    break;
                }
            }
            return pNode;
        }
        bool Insert(const K& key, const V& value)
        {
            PNode pNode = _pRoot;
            if (_pRoot == nullptr)
            {
                _pRoot = new Node(key, value);
                return true;
            }
            while (pNode != nullptr)
            {
                if (pNode->_key < key)
                {
                    if (pNode->_pRight == nullptr)
                    {
                        pNode->_pRight = new Node(key, value);
                        return true;
                    }
                    pNode = pNode->_pRight;
                }
                else if (pNode->_key > key)
                {
                    if (pNode->_pLeft == nullptr)
                    {
                        pNode->_pLeft = new Node(key, value);
                        return true;
                    }
                    pNode = pNode->_pLeft;
                }
                else
                {
                    pNode = nullptr;
                    break;
                }
            }
            return false;
        }
        void InOrder()
        {
            InOrderR(_pRoot);
        }
        void InOrderR(PNode pNode)
        {
            if(pNode == nullptr)
            {
                return ;
            }
            InOrderR(pNode->_pLeft);
            cout << pNode->_key << "::" << pNode->_value << endl;
            InOrderR(pNode->_pRight);
        }
        bool erase(const K&_key)
        {
            PNode parent = _pRoot;
            PNode curnode = _pRoot;
            while(curnode)
            {
                if(curnode->_key>_key)
                {
                    parent = curnode;
                    curnode = curnode->_pLeft;
                }
                else if(curnode->_key<_key)
                {
                    parent = curnode;
                    curnode = curnode->_pRight;
                }
                else//开始删除
                {
                    if(curnode->_pLeft==nullptr)
                    {
                        if(curnode==_pRoot)
                        {
                            _pRoot=curnode->_pRight;
                        }
                        else
                        {
                            if(parent->_pLeft==curnode)
                            {
                                parent->_pLeft = curnode->_pRight;

                            }
                            else
                            {
                                parent->_pRight = curnode->_pRight;
                            }
                        }
                    }
                    else if(curnode->_pRight==nullptr)
                    {
                        if(curnode==_pRoot)
                        {
                            _pRoot=curnode->_pLeft;
                        }
                        else
                        {
                            if(parent->_pLeft==curnode)
                            {
                                parent->_pLeft = curnode->_pLeft;
                            }
                            else
                            {
                                parent->_pRight = curnode->_pLeft;
                            }
                        }
                    }
                    else
                    {
                        PNode Child_pLeft = curnode->_pRight;
                        parent = curnode;
                        while(Child_pLeft->_pLeft)
                        {
                            parent = Child_pLeft;
                            Child_pLeft = Child_pLeft->_pLeft;
                        }
                        swap(Child_pLeft->_key,curnode->_key);
                        if(Child_pLeft==parent->_pLeft)
                        {
                            parent->_pLeft = Child_pLeft->_pRight;
                        }
                        else
                        {
                            parent->_pRight = Child_pLeft->_pRight;
                        }
                        delete Child_pLeft;
                        Child_pLeft = nullptr;
                    }
                    
                    return 1;
                }
            }
            return 0;
        }
        
};
